# 归并排序，利用递归的一种东西好像，分而治之
# 这个程序写着就挺厉害的。比较喜欢，以后估计还要继续查看，多记忆理解
def mergeSort(alist):
    print('Spliting:',alist)    # 打印要划分的列表

    if len(alist) > 1:
        mid = len(alist)//2 # 中间值
        leftList = alist[:mid]
        rightList = alist[mid:]
        mergeSort(leftList)
        mergeSort(rightList)    # 左右部分都排序，接着将左右部分进行合并

        i = 0
        j = 0   # 遍历左右两个分列表
        k = 0   # 结果列表
        while i < len(leftList) and j < len(rightList):
            if leftList[i] < rightList[j]:  # 小的先添加进结果
                alist[k] = leftList[i]
                i = i + 1
            else:
                alist[k] = rightList[j]
                j = j + 1
            k = k + 1

        while i < len(leftList):
            alist[k] = leftList[i]
            k = k + 1
            i = i + 1
        while j < len(rightList):
            alist[k] = rightList[j]
            k = k + 1
            j = j + 1

    print('merging',alist)

if __name__ == '__main__':
    alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
    mergeSort(alist)
    print(alist)
